class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None # 左孩子 left child
        self.rchild = None
        self.parent = None



class BST:
    def __init__(self):
        self.root = None

    # 递归
    def insert(self,node,val):
        if not node:
            node = BiTreeNode(val)
        elif val > node.data:
            node.rchild = self.insert(node.rchild,val)
            node.rchild.parent = node
        elif val < node.data:
            node.lchild = self.insert(node.lchild,val)
            node.lchild.parent = node
        return node

    # 非递归
    def insert_(self,val):
        p = self.root
        if not p:
            self.root = BiTreeNode(p)
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p

            if val < p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p

    def search(self,node,val):
        if not node:
            return None
        if node.data < val:
            return self.search((node.rchild),val)
        elif val < node.data:
            return self.search((node.lchild),val)
        return node

    def search_(self,val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif val < p.data:
                p = p.lchild
            else:
                return None
        return p